package com.congee02;

import java.util.Stack;

public class ReorderList_Stack {

    // 1. fast, slow -> mid, mid & stack
    // 2. fast, slow -> mid, 指针向中间汇聚
    public void reorderList(ListNode head) {
        if (head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        Stack<ListNode> reverse = new Stack<>();
        ListNode t = slow;
        while (t != null) {
            reverse.push(t);
            t = t.next;
        }

        ListNode p = head;

        // 避免循环判断head
        ListNode dummy = new ListNode(-1);

        while (! reverse.isEmpty()) {
            ListNode step = p.next;

            dummy.next = p;
            dummy = dummy.next;
            dummy.next = reverse.pop();
            dummy = dummy.next;

            p = step;
        }

        p.next = null;

        if (fast != null) {
            ListNode tail = head;
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = slow;
            slow.next = null;
        }
    }

    public static void main(String[] args) {
        ListNode composed = LeetcodeUtils.compose(1, 2, 3, 4, 5);
        new ReorderList_Stack().reorderList(
                composed
        );
    }

}
